/*
 * @lc app=leetcode.cn id=1046 lang=javascript
 *
 * [1046] 最后一块石头的重量
 */

// @lc code=start
class MaxHeap {
  constructor() {
    this.data = [0];
    this.count = 0;
  }

  buildHeap(stone) {
    this.count++;
    this.data[this.count] = stone;
    let i = this.count;
    while (parseInt(i / 2) > 0 && this.data[i] > this.data[parseInt(i / 2)]) {
      this.swap(i, parseInt(i / 2));
      i = parseInt(i / 2);
    }
  }

  swap(i, j) {
    let temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }

  popTop() {
    let top = this.data[1];
    this.data[1] = this.data[this.count];
    this.data.splice(this.count, 1)
    this.count--;
    let i = 1;
    while (true) {
      let maxPos = i;
      if (i * 2 <= this.count && this.data[i] < this.data[i * 2]) {
        maxPos = i * 2;
      }
      if (i * 2 + 1 <= this.count && this.data[maxPos] < this.data[i * 2 + 1]) {
        maxPos = i * 2 + 1;
      }
      if (i === maxPos) {
        break;
      }
      this.swap(i, maxPos);
      i = maxPos;
    }
    return top;
  }

  heapEmpty() {
    return this.count === 0;
  }

  onlyOne() {
    return this.count === 1;
  }

  getTop() {
    return this.data[1];
  }
}

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  let maxHeap = new MaxHeap();
  for (let i = 0; i < stones.length; i++) {
    maxHeap.buildHeap(stones[i])
  }
  while (true) {
    if (maxHeap.heapEmpty()) {
      return 0;
    }
    if (maxHeap.onlyOne()) {
      return maxHeap.getTop();
    }
    let y = maxHeap.popTop();
    let x = maxHeap.popTop();
    if (x !== y) {
      maxHeap.buildHeap(y - x)
    }
  }
};
// @lc code=end

